264B - Good Sequences - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int h = 1e5;
int primeFactors[h + 1];
void seive()
{
  for (int i = 0; i <= h; i++)
    primeFactors[i] = i;
  for (int i = 2; i <= h; i++)
  {
    if (primeFactors[i] == i)
    {
      for (int j = 2 * i; j <= h; j += i)
      {
        if (primeFactors[j] == j)
          primeFactors[j] = i;
      }
    }
  }
}
void solve()
{
  int n;
  cin >> n;
  int arr[n];
  map<int, int> mp;
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
    mp[arr[i]] = i;
  }
  // int dp[n];    // dp[i] : longest len of seq , ending at i.
  int d[h + 1]; //
  for (int i = 0; i <= h; i++)
    d[i] = 0;

  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    if (arr[i] == 1)
    {
      d[1] = 1;
      ans = max(ans, 1);
      continue;
    }
    int x = arr[i];
    int mx = 0;
    while (x > 1)
    {
      int div = primeFactors[x];
      d[div] += 1;
      mx = max(mx, d[div]);
      while (x % div == 0)
      {
        x /= div;
      }
    }
    x = arr[i];
    while (x > 1)
    {
      int div = primeFactors[x];
      d[div] = mx;
      while (x % div == 0)
      {
        x /= div;
      }
    }
    ans = max(ans, mx);
  }
  // cout << endl;
  cout << ans << endl;
}

int main()
{

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  seive();
  solve();

  return 0;
}